1. Field of the Invention
The present invention relates to an optimizing apparatus, an optimizing method, and a storage medium.
2. Description of the Related Art
Optimization forms the base of an intellectual process in the use of a highly advanced computer. Its specific application fields are, for example, the scheduling problem, the vehicle allocation problem, the pattern estimation problem, the automatic timetable assignment problem, the crew positioning problem, etc. However, since a limitation is imposed on a calculation amount or a storage apparatus capacity, it is not practical to solve such large-scale optimization problems by a search of all solutions.
As computer performance has been improving, closer attention is being paid to stochastic optimization methods (simulated annealing, a GA (Genetic Algorithm), etc.) as a means for solving a problem that is difficult to be solved with a conventional expert system etc., and studies have been made to put the methods into practical use. Especially, a GA attracts a great deal of attention among various optimization methods because of its simplicity.
Furthermore, personnel scheduling is a fundamental problem in all industries. This can be understood as one of optimization problems. This problem has a critical influence on cost reduction.
For example, in an aviation field, labor costs rank second to fuel costs on a worldwide scale. A reduction in labor costs is a significant challenge.
As a normal method for solving a combinatorial problem, modeling using simultaneous equations and mathematical solution seeking, such as LP (Linear Programming) and IP (Integer Programming) methods, etc., are utilized, and a problem is solved as a set partitioning problem or a set covering problem.
With these methods, however, putting of a complicated problem into definite equations itself is difficult when the problem is solved. For a large-scale problem, a solution cannot be obtained within a practical time due to an increase in the number of definitions or combinations, even if the problem can be put into equations. Besides, a solution cannot sometimes be found even after a search is executed for many hours.
Furthermore, methods such as column generation, etc. are used to increase speed. However, a large-scale problem faces various limitations owing to issues such as a column generation time, a restriction on a memory capacity, etc.
A method which attracts keen interest as a means for solving such problems associated with conventional methods is a GA (Genetic Algorithm) With the GA, a problem is put into a model, and its parameters are represented by using a chromosome. When optimization is made with a GA, a chromosome is decoded and converted into parameters, which are then entered into the problem model. The problem model is evaluated, and its evaluation value is used as a fitness of the chromosome, so that an individual (chromosome) is evolved and optimization is advanced.
Issues in conventional methods are listed below.
1. Issues in a Problem Description
With IP/LP, the problem description must be represented in a matrix form, and it is difficult to reflect the details of each condition with this method.
With some problem-solving methods using column generation, the problem is represented as a set of rules, and the details of the problem are described as generation rules at the time of column generation. However, there are various issues such as how to represent the problem by rules, how to verify coverage or appropriateness of rules, how to maintain consistency of rules, etc.
2. Issues in a Search Method
Even with a GA, which has advantages that are not implemented by conventional methods, its solution-seeking capability has the following limitations if a solution space becomes extremely large.
1) A GA chromosome cannot cover an entire solution space.
2) If coding is performed to cover an entire solution space, the number of areas, as such as the one causing a constraint violation or the one that is unsuitable as a solution, significantly increases. Therefore, optimization cannot efficiently be made.
3) Solution generation with solution generation rules is desirable in some cases. However, if a solution is generated by simply using the rules, a solution-seeking method becomes inflexible, so that a solution of high quality cannot be obtained.
3. Issues in a Scheduling Time Period and Operation Regularity
An actual target to be scheduled can be a rather complicated issue, such as whether a particular operation is to be or not to be performed depending on a day. With conventional methods, it is difficult to directly handle such a target. Therefore, the conventional techniques implicitly assume that the same operation is repeated for consecutive days, and draw up a schedule covering several days. This is referred to as a daily model.
Since operations to be scheduled become increasingly irregular hereafter, a solution to a daily model, etc., becomes increasingly unsuitable to the current status.
Also, as in the case of a flight crew schedule in the United States (US), a schedule such that some operations are not performed on weekends may be considered. This is referred to as a weekly model.
Furthermore, a schedule such that all of irregular schedule targets are included, and its time period is approximately 1 to 2 months is referred to as a fully dated model. An example of directly handling this model is not known.
An object of the present invention is to implement an optimizing apparatus, an optimizing method, and a storage medium, which can automatically generate a solution to a constraint satisfying an optimization problem that cannot conventionally be solved, and has not only an extensive search space but also many constraints conditions, such as a fully dated model.
An optimizing apparatus according to the present invention comprises the following units.
A solution-seeking data presenting unit outputs solution-seeking data to a problem model, and advances optimization of the solution-seeking data by receiving an evaluation value of a solution resultant from applying the solution-seeking data to the problem model.
A solution seeking unit obtains a solution-seeking starting point of a solution to the problem model from the solution-seeking data received from the solution-seeking data presenting unit, and seeks a solution to the problem model by using at least both a local search method and a stochastic search method.
An evaluation value calculating unit calculates an evaluation value of the solution sought by the solution seeking unit, and outputs the calculated value to the solution-seeking data presenting unit.
A solution obtaining unit obtains a final solution to the problem model by controlling the solution-seeking data presenting unit, the solution seeking unit, and the evaluation value calculating unit.
With the optimizing apparatus having the above described configuration, a search starting point in a solution space (search space) is globally determined according to the solution-seeking data, and the search space is restricted. Next, a solution is searched locally or stochastically from the search starting point (solution-seeking starting point) with local search and stochastic search methods. Therefore, according to the present invention, a search method is modified so that a search space can efficiently be searched in a large-scale problem. As a result, it becomes possible to obtain a solution to a complicated constraint satisfying optimization problem that cannot conventionally be solved, and has an extremely large search space and many constraint conditions, such as a fully dated model. Additionally, a solution can be obtained by a fewer number of search times than that of a conventional apparatus, thereby making a solution seeking time shorter than that of the conventional apparatus.
The solution-seeking data presenting unit represents solution-seeking data, for example, as a chromosome, and receives an evaluation value as a fitness of the chromosome, and advances the optimization of the solution-seeking data while evolving the chromosome with a genetic algorithm. In such a configuration, the solution seeking unit determines a solution-seeking starting point of a solution to a problem model by using a first probability table (such as a segmentation probability table to be described later, etc.) storing the information for stochastically determining the solution-seeking starting point, for example, when decoding a first gene of the chromosome. Furthermore, the solution seeking unit advances the solution seeking by decoding, for example, a second gene of the chromosome.
The solution seeking unit comprises a second probability table storing the information for stochastically determining the next search point, and advances the solution-seeking with a stochastic search method while using the second probability table (such as a segment connection probability table to be described later, etc.).
The problem model is, for example, a model of a constraint satisfying optimization problem seeking a solution of a second schedule over a plurality of days, which is obtained by linking a plurality of first schedules each composed of a sequence of operations in certain units for each day. The solution seeking starting point is an operation that is started at the beginning of the second schedule.
In such a configuration, the operations are, for example, on-board operations of a flight crew. In this case, the first schedule is a crew pattern on one day, and the second schedule is a crew pattern over a plurality of days. In such a case, the local search method is used to search for a connecting flight that can be operated on days except for those on which an irregular flight is in service. The stochastic search method is used to search for the next connecting flight.
The solution seeking unit generates a crew pattern by partitioning a ship line into segments based on the solution-seeking data, and by connecting the partitioned segments. The partitioning of the segments is made, for example, by using a segmentation probability table which is arranged for each ship line and stores the method partitioning each ship line.
Additionally, the connection of the partitioned segments is made, for example, by a stochastic search using a segment connection probability table which is arranged for each flight and stores connection probability information of flights to be connected to each flight.
The solution-seeking data is given as a chromosome obtained with a genetic algorithm. In this case, the solution-seeking data presenting unit evolves the chromosome with a genetic algorithm. The solution seeking unit generates a crew pattern by using the chromosome. The evaluation value calculating unit calculates the evaluation value of the crew pattern generated by the solution seeking unit as a fitness of the chromosome.
According to another preferred embodiment in the case where the solution-seeking data is given as a chromosome obtained with a genetic algorithm, a solution seeking unit generates a crew pattern by partitioning each ship line into segments with a first gene of the chromosome, and a segmentation probability table which is arranged for each ship line and stores the information for stochastically determining a partitioning method of each ship line, and by connecting the partitioned segments.
In such a preferred embodiment, the solution seeking unit stochastically searches for a segment to be connected next by using a second gene of the chromosome, and a segment connection probability table which is arranged for each flight and stores a connection probability value of a flight to be connected to each flight.
An optimizing method obtaining a final solution to a problem model according to the present invention comprises: outputting solution-seeking data to a problem model, and advancing optimization of the solution-seeking data by receiving an evaluation value of a solution obtained by applying the solution-seeking data to the problem model; obtaining a solution-seeking starting point of a solution to the problem model from the solution-seeking data, and seeking the solution to the problem model by using at least both of a local search method and a stochastic search method; and calculating an evaluation value of the obtained solution, and using the calculated evaluation value to advance optimization of the solution-seeking data.
A computer-readable storage medium obtaining a final solution to a problem mode according to the present invention, on which is recorded a program for causing a computer to execute a process, said process comprising: outputting solution-seeking data to a problem model, and advancing optimization of the solution-seeking data by receiving an evaluation value of a solution obtained by applying the solution-seeking data to the problem model; obtaining a solution seeking-starting point of a solution to the problem model, and seeking the solution to the problem model by using at least both of a local search method and a stochastic search method; and calculating an evaluation value of the obtained solution, and using the calculated evaluation value to advance optimization of the solution-seeking point.